'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-11 09:45:40
'''
#
# @lc app=leetcode.cn id=514 lang=python3
#
# [514] 自由之路
#
'''
直接dp，状态是dp[i][j]表示key[i]，ringj，key[i]
与ring[j]对齐所需要的步数。转移方程就是 
dp[i][j] = min(dp[i-1][k]+min(abs(j-k), len(ring)-abs(k-j))) + 1，
k需要满足key[i-1]==ring[k]。所以开始用一个store存储
所有的key中的s对应ring中的脚标，在根据转移方程做循环就好了。
整体不复杂，代码也简单，效率还不错。空间优化没做，有兴趣的同学自己做。
'''

# @lc code=start
class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        import collections
        from sys import maxsize
        store = collections.defaultdict(list)
        for i, v in enumerate(ring):
            store[v].append(i)
        dp = [[maxsize]*(len(ring)) for _ in key]
        for j in store[key[0]]:
            dp[0][j] = min(j, len(ring)-j)+1
        for i in range(1, len(key)):
            for j in store[key[i]]:
                for k in store[key[i-1]]:
                    dp[i][j] = min(dp[i][j], dp[i-1][k]+min(abs(j-k), len(ring)-abs(j-k))+1)
        return min(dp[-1])
# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    ring = "pqwcx"
    key = "cpqwx"
    print(solution.findRotateSteps(ring, key))
